【题解】 最长上升子序列 状压DP bzoj3591 | Qiuly's blog!

【题解】 最长上升子序列 状压DP bzoj3591

Posted on | In | Comments:

这题脑洞很大——你需要状压 $\rm{LTS}$ 数组，而且是三进制状压。复杂度很高……大约是 $O(n3^n)$ 左右，当然实际复杂度会小于这个，$1000^+ms$ 是可以通过的。

对于每一个数字，分别记录其三种状态：该数字没有进过 $\rm{LTS}$ 数组记为 $0$ ，该数字在 $\rm{LTS}$ 数组中记为 $1$ ，该数字进过 $\rm{LTS}$ 数组，结果又出来了记为 $2$ 。

设 $f_i$ 表示 $1$ 到 $n$ 所有数字的状态为 $i$ 时的方案数，接下来考虑转移，首先对于这个 $i$ 状态我们还原其 $\rm{LTS}$ 数组，也就是当前位置上为 $1$ 的那些数字。接着我们枚举所有位置上为 $0$ 的数字，并考虑将其插入当前的 $\rm{LTS}$ 当中。替换掉一个状态为 $1$ 的数。

我们就选定这个要被替换的状态为 $1$ 的数为当前 $\rm{LTS}$ 中第一个大于当前要加入的数的数，那么这样替换后 $\rm{LTS}$ 依然满足其性质。

维护一个指针扫一遍就好，碰到需要换的数就将其标记为 $2$ ，然后将当前需要加入的数变成 $1$ 即可。

需要注意的是，我们这里的”加入”并不是只的在原数组中加入，也就是说跟排列什么的几乎扯不上关系，比如说当前序列为 $1,2,3,4,5$ ，$\rm{LTS}$ 数组为 $1,3,4$ ，我们在这里将 $3$ 丢掉，然后加入 $2$ ，其实是不变的。

当所有数字都被考虑过的时候就可以直接统计答案了，普通的 $\rm{LTS}$ 也是所有数字都要考虑一回的。

在做 $\rm{DP}$ 转移的时候我们顺带满足一下题面给出的那些数的递增即可，那么可以保证所有被统计的状态都带有题面要求的 $\rm{LTS}$ 。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=1e2+2;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

int n,m,ans,arr[N],pos[N],mul[N];
int hep[N],var[N],dp[14348907+3];

int main() {
    freopen("3591.in","r",stdin);
    freopen("3591.out","w",stdout);
    IN(n),IN(m);
    for(int i=0;i<m;++i) 
        IN(arr[i]),--arr[i],pos[arr[i]]=i;
    mul[0]=dp[0]=1;
    for(int i=1;i<=n;++i) mul[i]=mul[i-1]*3;
    for(int i=0;i<mul[n];++i) if(dp[i]) {
        int state=i,top=0,num=0,per=0;
        for(int j=0;j<n;++j) {
            var[j]=state%3,state/=3;
            if(var[j]) ++num;
            if(var[j]==1) hep[top++]=j;
        }
        if(num==n) {ans+=dp[i];continue;}
        for(int j=0;j<n;++j) {
            if(var[j]) continue;
            if(pos[j]&&!var[arr[pos[j]-1]]) continue;
            while(hep[per]<j&&per<top) ++per;
            if(per>=m) continue;
            state=i+mul[j];
            if(per<top) state+=mul[hep[per]];
            dp[state]+=dp[i];
        }
    }
    printf("%d\n",ans);
    return 0;
}

本文标题:【题解】 最长上升子序列 状压DP bzoj3591

文章作者:Qiuly

发布时间:2019年05月08日 - 00:00

最后更新:2019年05月08日 - 16:09

原始链接:http://qiulyblog.github.io/2019/05/08/[题解]bzoj3591/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。